The present invention relates to processor allocation generally, that is, to the problem of associating tasks with processing units in a computing system. The invention relates more particularly to associations made using derived task spaces and multidimensional task spaces.
Networks and other collections of connected processing units can be much more reliable than a single processing unit for a variety of reasons. When a processing unit fails, its tasks can be reassigned to working units, and new tasks can be diverted away from the failed unit. Tasks can often be performed faster by adding processing units and dividing tasks between processing units, which can then execute the tasks at least partially in parallel. Processing units include individual computer CPUs and supporting circuitry and software necessary for executing a task, as well as larger groups of processors such as multiprocessors and clusters.
One traditional method of associating tasks with processing units includes assigning a name or an ordinal number (sometimes referred to as a whole number or integer) to each task. A similar name or ordinal number is assigned to each processing unit. Names may be strings, enumeration values, or other familiar identifiers. Each task is then placed on a list associated with the assigned processing unit by placing its name, number, or other identifier on the list. Each processing unit thus has a list of the tasks it needs to perform. When a processing unit is added to the computing system, tasks must be explicitly sent to the new server. If existing tasks are among those sent, their identifiers must be located in the existing server list, deleted, and then reassigned to a new server. When a processing unit fails, tasks in the failed server""s list must be located, deleted and then reassigned to a new server.
One variation assigns a fractional number (sometimes referred to as a real number) to each task and a range of fractional values to each processing unit. For instance, each task could be assigned a fraction in the interval [0, 1] on the real number line using the familiar Euclidean metric, with each processing unit being assigned a subinterval within that range. A given task is then associated with a given processing unit if the interval allocated to the processing unit contains the fraction assigned to the task.
With either approach, load balancing may be used to spread tasks evenly among servers or other processing units. Load balancing algorithms determine where to assign each task so that the collection of tasks and processing units satisfies some criterion such as finishing as quickly as possible. To achieve high reliability of the network as a whole, tasks assigned to failed servers are rebalanced across operating servers. This may require redistributing the list associated with a failed processing unit among the currently working processing units. Making, maintaining, and redistributing the lists is a relatively expensive operation. Distributed networks must often execute complicated distributed algorithms using imperfect knowledge to approximate optimal bandwidth, and task lists must often be kept in multiple places to facilitate recovery from failures.
A drawback of the approach that assigns fractions in [0 . . . 1] to tasks is that assigning the fractions may require difficult or arbitrary choices, because only a single fraction value is assigned to a given task. All servers that might be eligible to receive the task must likewise be characterized in the same way, namely, according to the single criterion that was used when characterizing the task by assigning it a fraction value.
Thus, it would be an advancement in the art to provide improved ways to associate tasks with server computers and other processing units so that creating and maintaining conventional task lists is unnecessary.
It would also be an advancement to provide improved ways to associate tasks with processing units such that the tasks and the processors may be characterized according to several criteria.
It would be an additional advancement to provide such improvements which extend the capabilities of existing processor allocation mechanisms, and hence can be used in conjunction with existing mechanisms.
Such improvements are disclosed and claimed herein.
The present invention provides improved tools and techniques for associating tasks with server computers and other processing units. In one embodiment, a computer-implemented method begins by allocating a region within a derived metric space such as a Hausdorff task space with a Hausdorff or other metric, and then assigning a non-empty subset of the task space to each task. Each task is then assigned to the processing unit whose region is closestxe2x80x94in the given metricxe2x80x94to the task""s assigned subset. In another embodiment, a computer-implemented method begins by allocating a region within a multidimensional task space which is a complete space having an associated metric, and then assigning each task a point in the space. If the region allocated to the processing unit includes the point which has been assigned to the task, then the task is associated with the processing unit.
Thus, some embodiments avoid giving tasks an identity by assigning a name or a single ordinal number or a single real value. Instead, each task is assigned multiple values for identification, at least for purposes of matching tasks with processing units. Likewise, some embodiments avoid giving processing units an identity by assigning a name or a single ordinal number or a single real value. Instead, each processing unit is assigned a multi-valued and/or multidimensional region. A task or a processing unit may, of course, have other identifiers used for other purposes; the focus here is on identifiers used for processor allocation.
Multidimensional and/or derived task spaces are termed xe2x80x9cmulti-facetedxe2x80x9d. A xe2x80x9cpointxe2x80x9d in a multi-faceted task space may thus be multidimensional in some embodiments and one-dimensional in others. A xe2x80x9csubsetxe2x80x9d assigned to a task may be limited to a single point in some embodiments and be allowed to contain multiple points in other embodiments. The xe2x80x9ccomponentxe2x80x9d value(s) within a point represent the position of the point within the dimension(s) of the task space. Point components may be real or fractional values, and points may include a mixture of such real values with enumerated or ordinal values.
Stated differently, some embodiments each use a derived space as the multi-faceted task space, such as the Hausdorff space (with a Hausdorff or other metric) derived from a foundation space. These derived spaces may be one-dimensional or multidimensional. They include the Hausdorff space derived from the real interval [0 . . . 1], the Hausdorff space derived from the two-dimensional foundation space [0. . . 1]xc3x97[0 . . . 1], and Hausdorff spaces derived from crossing the real line R and/or real intervals from R to obtain a space of N-dimensional points, and spaces derived from other foundation spaces. The terms xe2x80x9cderived spacexe2x80x9d and xe2x80x9cHausdorff spacexe2x80x9d are used as synonyms herein (note, however, that a derived space need not use a Hausdorff metric). In these spaces, each task may be assigned one or more points of the foundation space, since a point in the derived space is a non-empty subset of the foundation space points. Each processing unit is allocated a region which is a not-necessarily-connected subset of the foundation space points.
Other embodiments do not necessarily use derived (Hausdorff) spaces, but use a multidimensional space as the multi-faceted task space. For instance, such embodiments include the two-dimensional space derived from [0 . . . 1]xc3x970 . . . 1] with the familiar Euclidean metric, and higher dimensional Hausdorff spaces derived from crossing the real line R and/or real intervals from R to obtain a space of N-dimensional points. In these spaces, each task may be one (multidimensional) point of the foundation space. Each processing unit is again allocated a region which is a subset of the foundation space points.
As noted, in some embodiments more than one point may be associated with a given task. The point set which identifies a task can be chosen at random. However, it may also represent nominal values in an environment chosen to make the task execute more efficiently.
Processing units are allocated a subset of the task space. A given task is routed to a server or other processing unit whose region is closest to the points) assigned to the tasks. Tasks may be similarly associated with a wait condition or a suspended state, when one or more of their assigned points fall within and/or close to regions allocated to such conditions or states.
In short, the present invention provides improved tools and techniques for associating tasks with processing units. The mathematics used by the invention for the specific job of associating tasks with processing units is more general than the math used in conventional systems, but the invention can assist processor allocation, load balancing, and related administrative jobs. The invention also allows tasks and processors to be characterized by multiple criteria, because multiple dimensions and/or derived spaces can be used to define task points and processor regions. This allows tradeoffs that were not possible in conventional one-dimensional systems. Other features and advantages of the invention will become more fully apparent through the following description.